CVE-2020-16040: Chromium V8引擎整数溢出漏洞分析
V8是Chromium内核中的JavaScript引擎，负责对JavaScript代码进行解释优化与执行，而CVE-2020-16040(crbug.com/1150649)是V8优化编译器Turbofan在SimplifiedLowering阶段产生的一个整数溢出漏洞。
1）Turbofan是什么？
下面是V8引擎的工作流程：
Parser(解析器)：负责通过对源代码进行词法分析得到的token对源代码进行语法错误分析、转换为AST抽象语法树并确定词法作用域：
Ignition(解释器)：负责将 AST 转换为中间代码即字节码(Bytecode)并逐行解释执行字节码，在该阶段， JavaScript 代码就已经开始执行了。
考虑如下代码bytecode.js：
let ziwu_add = (x,y) => {return x + y;}ziwu_add(1,2)使用命令./d8 bytecode.js --allow-natives-syntax --print-bytecode --print-bytecode-filter ziwu_add可得到其字节码：
[generated bytecode for function: ziwu_add (0x1984082d26e1 <SharedFunctionInfo ziwu_add>)]Parameter count 3Register count 0Frame size 00x1984082d2826 @ 0 : 25 04 Ldar a10x1984082d2828 @ 2 : 35 03 00 Add a0, [0]0x1984082d282b @ 5 : ab Return Constant pool (size = 0)Handler Table (size = 0)Source Position Table (size = 0)Add a0, [0]即字节码，他告诉V8我们是要执行一个加法操作。
TurboFan(优化编译器)：负责将字节码和一些分析数据作为输入并生成优化的机器代码，当 Ignition 将 JavaScript 代码转换为字节码后，代码开始执行，V8 会一直观察 JavaScript 代码的执行情况，并记录执行信息，如每个函数的执行次数、每次调用函数时，传递的参数类型等。如果一个函数被调用的次数超过了内设的阈值，监视器就会将当前函数标记为热点函数（Hot Function），并将该函数的字节码以及执行的相关信息发送给 TurboFan。TurboFan 会根据执行信息做出一些进一步优化此代码的假设，在假设的基础上将字节码编译为优化的机器代码。如果假设成立，那么当下一次调用该函数时，就会执行优化编译后的机器代码，以提高代码的执行性能。当某一次调用传入的信息变化时，表示 TurboFan 的假设是错误的，此时优化编译生成的机器代码就不能再使用了，于是进行优化回退，重走原复杂函数逻辑。
优化逻辑过程如下，考虑下述代码：
let ziwu_add = (x,y) => {return x + y;}ziwu_add(1,2);ziwu_add('hack','you');ziwu_add([],{})V8在每次计算时需要先判断x、y的类型，然后执行相应的处理，但如果该函数要执行很多次呢？
let ziwu_add = (x,y) => {return x + y;}for (var i=0;i<0x10000;i++){ ziwu_add(1+i,2)}x参数持续变化，如果每次都要去判断类型是否过于繁琐，不够高效，Turbofan通过观察发现，经过了如此多的循环计算，x、y参数都是int类型，有理由相信下一次应该还是这样，那就不妨将x、y参数的类型假设为int，基于这个假设，我们可以将ziwu_add函数优化为简单的加法：
add eax ebx;2）漏洞复现
先看漏洞补丁:https://chromium.googlesource.com/v8/v8.git/+/ba1b2cc09ab98b51ca3828d29d19ae3b0a7c3a92，漏洞文件位于src/compiler/simplified-lowering.cc，即该漏洞可能发生在Turbofan优化过程的SimplifiedLowering阶段;
我们将V8版本切换到其parent commit处，即存在该漏洞的最近的V8代码分支版本，操作方法不在此赘述:
执行PoC代码./d8 --allow-natives-syntax poc.js
function foo(a) {var y = 0x7fffffff; // 2^31 - 1// Widen the static type of y (this condition never holds).if (a == NaN) y = NaN;// The next condition holds only in the warmup run. It leads to Smi// (SignedSmall) feedback being collected for the addition below.if (a) y = -1;const z = (y + 1)|0;return z<0; }console.log(foo(false));for (i=0;i<0x10000;i++){ foo('test') }console.log(foo(false));我们得到的结果是:
TrueFalse两次foo(false)函数执行结果不同，说明Turbofan优化过程对z<0表达式的结果判断出现了问题
3）原理解析
原理简述: 该漏洞实际上是由于在VisitSpeculativeIntegerAdditiveOp函数中，对SpeculativeSafeIntegerAdd节点优化时计算出的最大取值范围(restriction_type)与其自身Type不一致导致在后续的SpeculativeNumberLessThan节点优化过程中发送错误的类型传递，使得SpeculativeNumberLessThan被错误优化为Uint32LessThan，于是在EarlyOptimization阶段发生了错误的常量折叠，导致与优化前计算不一致。
详细分析:
1.优化前foo(false)函数执行为True原因分析：
y = 0x7fffffff即32位的最大整数，z = (0x7fffffff +1) | 0
由于按位与操作是将其操作数（operands）当作32位的比特序列（由0和1组成）进行执行，则(0x7fffffff +1) = -2147483648
z = -2147483648|0 ， z必然小于0，foo函数执行结果为true
2.Turbofan优化过程出现计算错误：
我们首先使用for循环去强制触发Turbofan的优化：
for (i=0;i<0x10000;i++){ foo('test') }Turbofan优化过程首先会进入SimplifiedLowering阶段，通过正反向遍历确定字节码树(Bytecode Graph Tree)中各节点的输入类型、输出类型、最大取值范围等，其共分为三个⼦阶段Propagate、Retype、Lower[1]。
我们先来看看在本例中SimplifiedLowering如何优化我们的foo函数：
1) Propagate阶段：我们可以使用./d8 --allow-natives-syntax poc.js --trace-representation来查看整个PoC脚本的Propagate过程：
--{Propagate phase}-- visit #48: End (trunc: no-value-use) initial #47: no-value-use visit #47: Return (trunc: no-value-use) initial #44: truncate-to-word32 initial #55: no-truncation (but distinguish zeros) initial #45: no-value-use initial #36: no-value-use visit #55: NumberLessThan (trunc: no-truncation (but distinguish zeros)) initial #45: truncate-to-word32 initial #44: truncate-to-word32 visit #45: SpeculativeNumberBitwiseOr (trunc: truncate-to-word32) initial #43: truncate-to-word32 initial #44: truncate-to-word32 initial #43: truncate-to-word32 initial #36: no-value-use visit #43: SpeculativeSafeIntegerAdd (trunc: truncate-to-word32) initial #39: no-truncation (but identify zeros) initial #42: no-truncation (but identify zeros) initial #22: no-value-use initial #36: no-value-use ...该阶段为逆向分析，从End节点到Start节点，根据输⼊节点的Type确定所需的类型，并给相关节点关联其使用信息(UseInfo) 。并标记该节点的输出类型作为输出的最大取值范围restriction_type。
在对foo函数的优化过程中会首先访问kSpeculativeNumberBitwiseOr#45节点，如下图所示：
根据src/compiler/simplified-lowering.cc代码逻辑，进而调用VisitSpeculativeInt32Binop函数,由于#45节点的两个输入节点 #43/#44都是Number类型，于是BothInputsAre(node, Type::NumberOrOddball())条件成立，进而turbofan将#43/#44标记为UseInfo::TruncatingWord32():
case IrOpcode::kSpeculativeNumberBitwiseOr:case IrOpcode::kSpeculativeNumberBitwiseXor:case IrOpcode::kSpeculativeNumberBitwiseAnd: VisitSpeculativeInt32Binop<T>(node);void VisitSpeculativeInt32Binop(Node* node) { DCHECK_EQ(2, node->op()->ValueInputCount());if (BothInputsAre(node, Type::NumberOrOddball())) {return VisitBinop<T>(node, UseInfo::TruncatingWord32(), <===此处 MachineRepresentation::kWord32); }然后继续访问SpeculativeSafeIntegerAdd#43节点，由于我们在PoC中为该节点的输入y扩充了类型if (a == NaN) y = NaN;即#39节点存在NaN类型，我们可以通过--trace-representation选项观察到这一现象：
#39:Phi[kRepTagged](#32:Phi, #38:NumberConstant, #36:Merge) [Static type: (NaN | Range(-1, 2147483647))] visit #39: Phi ==> output kRepFloat64因此在src/compiler/simplified-lowering.cc::VisitSpeculativeIntegerAdditiveOp函数中if条件不成立，进而将自身的最大取值范围restrict_type设置为Signed32()，即-2147483648 ~2147483647
void VisitSpeculativeIntegerAdditiveOp(Node* node, Truncation truncation, SimplifiedLowering* lowering) { ...if (left_upper.Is(left_constraint_type) && right_upper.Is(Type::Signed32OrMinusZero()) && (left_upper.Is(Type::Signed32()) || right_upper.Is(Type::Signed32()))) { VisitBinop<T>(node, UseInfo::TruncatingWord32(), MachineRepresentation::kWord32, Type::Signed32()); } else { ... VisitBinop<T>(node, left_use, right_use, MachineRepresentation::kWord32, <===此处 Type::Signed32()); }但我们可以观察到此时SpeculativeSafeIntegerAdd#43节点的Type为0 ～2147483648
#43:SpeculativeSafeIntegerAdd[SignedSmall](#39:Phi, #42:NumberConstant, #22:SpeculativeNumberEqual, #36:Merge) [Static type: Range(0, 2147483648), Feedback type: Range(0, 2147483647)] visit #43: SpeculativeSafeIntegerAdd ==> output kRepWord322) Retype阶段：同样的我们可以继续使用--trace-representation来查看Retype的过程：
--{Retype phase}-- visit #5: HeapConstant ==> output kRepTaggedPointer visit #0: Start ==> output kRepTagged visit #7: OsrValue ==> output kRepTagged visit #20: StateValues ==> output kRepTagged visit #21: StateValues ==> output kRepTagged visit #22: HeapConstant ==> output kRepTaggedPointer可以看出该阶段为正向分析，从End节点到Start节点依次送入栈，然后从栈顶开始，依次访问并根据输入节点的Type和restriction_type确定输出类型，并使用UpdateFeedbackType更新各节点类型,并计算各节点输入的输出表示形式(representation)
Turbofan首先访问SpeculativeSafeIntegerAdd#43节点，进入src/compiler/simplified-lowering.cc::UpdateFeedbackType函数逻辑，该节点opcode为IrOpcode::kSpeculativeSafeIntegerAdd：
根据src/compiler/opcodes.h
#define SIMPLIFIED_SPECULATIVE_NUMBER_BINOP_LIST(V) \V(SpeculativeNumberAdd) \ V(SpeculativeNumberSubtract) \ V(SpeculativeNumberMultiply) \ V(SpeculativeNumberDivide) \ V(SpeculativeNumberModulus) \ V(SpeculativeNumberBitwiseAnd) \ V(SpeculativeNumberBitwiseOr) \ V(SpeculativeNumberBitwiseXor) \ V(SpeculativeNumberShiftLeft) \ V(SpeculativeNumberShiftRight) \ V(SpeculativeNumberShiftRightLogical) \ V(SpeculativeSafeIntegerAdd) \ V(SpeculativeSafeIntegerSubtract)从而进入下列标记处逻辑，对#43节点的两个输入#39和#42节点的类型进行SpeculativeSafeIntegerAdd计算，再与自身restriction_type进行交集运算(Intersect)
bool UpdateFeedbackType(Node* node) { ...switch (node->opcode()) {#define DECLARE_CASE(Name) \case IrOpcode::k##Name: { \ new_type = op_typer_.Name(input0_type, input1_type); \break; \ } SIMPLIFIED_NUMBER_BINOP_LIST(DECLARE_CASE) DECLARE_CASE(SameValue)#undef DECLARE_CASE
#define DECLARE_CASE(Name) \case IrOpcode::k##Name: { \ new_type = Type::Intersect(op_typer_.Name(input0_type, input1_type), \ <===此处 info->restriction_type(), graph_zone()); \break; \ } SIMPLIFIED_SPECULATIVE_NUMBER_BINOP_LIST(DECLARE_CASE) SIMPLIFIED_SPECULATIVE_BIGINT_BINOP_LIST(DECLARE_CASE)#undef DECLARE_CASE进入src/compiler/operation-typer.cc::OperationTyper::SpeculativeSafeIntegerAdd函数：
Type OperationTyper::SpeculativeSafeIntegerAdd(Type lhs, Type rhs) { Type result = SpeculativeNumberAdd(lhs, rhs);return Type::Intersect(result, cache_->kSafeIntegerOrMinusZero, zone());}进入src/compiler/operation-typer.cc::OperationTyper::Speculative##Name逻辑：
#define SPECULATIVE_NUMBER_BINOP(Name) \Type OperationTyper::Speculative##Name(Type lhs, Type rhs) { \ lhs = SpeculativeToNumber(lhs); \ rhs = SpeculativeToNumber(rhs); \ return Name(lhs, rhs); \ }lhs = SpeculativeToNumber(lhs); => 即y参数-1 ~ 0x7fffffff
rhs = SpeculativeToNumber(rhs); => 即1
NumberAdd(lhs,rhs); => 0 ~ 0x7fffffff+1
交集运算：Intersect(0 ~ 0x7fffffff+1,restriction_type) =>Intersect(0 ~ 0x7fffffff+1,Signed32) => 0 ~ 0x7fffffff
即#43节点的取值范围为0 ~ 0x7fffffff即Unsigned32
再访问SpeculativeNumberBitwiseOr#45节点，根据输入节点#43/#44的类型得到的结果仍然是0 ~ 0x7fffffff，即PoC中z的取值范围被认为是0 ~ 0x7fffffff
3) Lower阶段：同样的我们可以继续使用--trace-representation来查看Lower的过程
--{Lower phase}-- visit #5: HeapConstant visit #0: Start visit #7: OsrValue visit #20: StateValues visit #21: StateValues visit #22: HeapConstant visit #6: OsrValue visit #23: Parameter visit #58: FrameState visit #70: HeapConstant visit #24: FrameState visit #146: Checkpoint visit #139: LoadFieldchange: #139:LoadField(@0 #70:HeapConstant) from kRepTaggedPointer to kRepTagged:no-truncation (but distinguish zeros)我们可以看出该阶段主要是做两件事情：
通过DeferReplacement将节点本身优化为更加具体的节点
当某节点输入的输出表示(representation,由Retype阶段得到)与其输入的预期使用信息(UseInfo)不匹配时使用ConvertInput转换节点
Turbofan访问SpeculativeNumberLessThan#46节点，进入src/compiler/simplified-lowering.cc以下逻辑：
case IrOpcode::kNumberLessThan:case IrOpcode::kNumberLessThanOrEqual: { Type const lhs_type = TypeOf(node->InputAt(0)); Type const rhs_type = TypeOf(node->InputAt(1));// Regular number comparisons in JavaScript generally identify zeros,// so we always pass kIdentifyZeros for the inputs, and in addition// we can truncate -0 to 0 for otherwise Unsigned32 or Signed32 inputs.if (lhs_type.Is(Type::Unsigned32OrMinusZero()) && rhs_type.Is(Type::Unsigned32OrMinusZero())) {// => unsigned Int32Cmp VisitBinop<T>(node, UseInfo::TruncatingWord32(), MachineRepresentation::kBit);if (lower<T>()) NodeProperties::ChangeOp(node, Uint32Op(node)); } else if (lhs_type.Is(Type::Signed32OrMinusZero()) && rhs_type.Is(Type::Signed32OrMinusZero())) {// => signed Int32Cmp VisitBinop<T>(node, UseInfo::TruncatingWord32(), MachineRepresentation::kBit); ...参考src/compiler/simplified-lowering.cc::Uint32Op
const Operator* Uint32Op(Node* node) {return changer_->Uint32OperatorFor(node->opcode()); }进入Uint32OperatorFor逻辑，源码位于src/compiler/representation-change.cc
const Operator* RepresentationChanger::Uint32OperatorFor( IrOpcode::Value opcode) {switch (opcode) {case IrOpcode::kNumberAdd:return machine()->Int32Add();case IrOpcode::kNumberSubtract:return machine()->Int32Sub();case IrOpcode::kSpeculativeNumberMultiply:case IrOpcode::kNumberMultiply:return machine()->Int32Mul();case IrOpcode::kSpeculativeNumberDivide:case IrOpcode::kNumberDivide:return machine()->Uint32Div();case IrOpcode::kSpeculativeNumberModulus:case IrOpcode::kNumberModulus:return machine()->Uint32Mod();case IrOpcode::kNumberEqual:case IrOpcode::kSpeculativeNumberEqual:return machine()->Word32Equal();case IrOpcode::kNumberLessThan:case IrOpcode::kSpeculativeNumberLessThan: <===此处return machine()->Uint32LessThan();case IrOpcode::kNumberLessThanOrEqual:case IrOpcode::kSpeculativeNumberLessThanOrEqual:return machine()->Uint32LessThanOrEqual();case IrOpcode::kNumberClz32:return machine()->Word32Clz();case IrOpcode::kNumberImul:return machine()->Int32Mul();default: UNREACHABLE(); }}因此#46节点被转换为Uint32LessThan
4) 漏洞触发: EarlyOptimization阶段
进入代码src/compiler/machine-operator-reducer.cc逻辑
case IrOpcode::kUint32LessThan: { Uint32BinopMatcher m(node);if (m.left().Is(kMaxUInt32)) return ReplaceBool(false); // M < x => falseif (m.right().Is(0)) return ReplaceBool(false); // x < 0 => false由于#46节点(即PoC中的z<0)的右输入节点为0，满足m.right().Is(0)条件，该表达式判定结果被判定为false。
3.优化后foo(false)函数执行为False原因分析:
结合第二步的分析，turbofan优化之后，表达式z<0被错误判定为false，因此foo(false)函数返回结果为false
该漏洞是turbofan优化过程产生的一个典型的逻辑漏洞，调试难度相对较低，适合V8初学者入门，通过源码去理解会有不错的效果，V8近年来还有很多类似的漏洞,如crbug.com/880207, 感兴趣的可以去调试学习。
行文不当之处还请各位读者斧正，欢迎交流。
[1]Modern attacks on the Chrome browser : optimizations and deoptimizations: https://buaq.net/go-45470.html
[2]漏洞修复代码: https://chromium.googlesource.com/v8/v8.git/+/ba1b2cc09ab98b51ca3828d29d19ae3b0a7c3a92